package swardToOffer.method_2_sort_or_find.find;

/**
 * @Author ChanZany
 * @Date 2021/5/20 15:50
 * @Version 1.0
 * 面试题11：旋转数组的最小数字
 * 题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 * 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组
 * {3, 4, 5|, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
 * 思路：二分查找法，根据旋转数组的特性，可以将其划分为两个递增数组进行查找
 * 设定两个指针分别指向数组的头尾，可以查找到中间元素，观察中间元素和头尾元素的大小关系，可以缩小搜索的范围
 * 以上面的例子，这个关系为：
 * 当中间元素大于头元素，则中间元素位于第一个递增子数组，最小数字一定位于它的后面
 * 否则位于第二个递增子数组，最小数字一定位于他的前面，
 */
public class MinNumberInRotatedArray {
   public int minNum(int[] nums){
        if (nums.length<=0) return -1;
        int left = 0;
        int right = nums.length-1;
        int mid = left;
       while (nums[left]>=nums[right]){
           if (right-left==1) {
               mid = right;
               break;
           }
           mid = (right-left)/2+left;
           if (nums[left]<=nums[mid]){
               left=mid;
           }else if (nums[mid]<=nums[right]){
               right=mid;
           }
        }
        return nums[mid];
   }


    public static void main(String[] args) {
        MinNumberInRotatedArray Main = new MinNumberInRotatedArray();
        System.out.println(Main.minNum(new int[]{3, 4, 5, 1, 2}));
    }

}
